%\subsection{Background}
%\missingfigure{System overview}



%\begin{figure}[hbpt]
%  \begin{center}
%  \includegraphics[width=0.95\linewidth]{figures/sysoverview}
%  \end{center}
%  \caption{System overview}
%  \label{fig:sim}
% \end{figure}


\begin{figure}
  \centering
  \subfloat[Preprocessing]{\label{fig:sysoverviewa}\includegraphics[scale=0.7]{figures/sysoverviewa}}                
  \subfloat[Prediction]{\label{fig:sysoverviewb}\includegraphics[scale=0.7]{figures/sysoverviewb}}
  \caption{System overview}
  \label{fig:sysoverview}
\end{figure}



\subsection{Preliminaries}
\label{sec:preliminaries}
In this paper we will only be considering undirected graphs with unique vertex labelings. Each vertex in a graph is assigned a label from an ordered, finite alphabet such that
no two vertices share the same label \cite{UniqueNodeLabels}. Formally, a graph is then a three-tuple $G=(V,E,\alpha)$ where $V$ is a finite vertex set, $E \subset V \times V$ is a finite edge set
and $\alpha : V \to \mathcal{L}$ is a vertex label mapping. We say that a graph $G$ has unique node labels if $\forall v,w \in V$ we have that  $v \neq w \Leftrightarrow \alpha(v) \neq \alpha(w)$.
Let $\mathcal{G}$ be the set of all formable graphs using the label alphabet $\mathcal{L}$.


Graph matching is in general a difficult problem due to high computational complexity. Algorithms for computing subgraph isomorphism, graph edit distance, smallest common subgraph etc are all NP-complete problems.
The fact that the graphs under consideration are equipped with unique node labels makes many of the notoriously NP-complete problems of graph theory tractable since they can be computed in
polynomial time. 


The \emph{graph edit distance} is a notion used to measure how similar two graphs are two each other. 
It is based upon what is called \emph{edit operations} on a graph. An edit operation is a change performed upon a graph to transform it into a new graph.
Normally one considers: vertex substitutions, vertex additions, edge additions, vertex deletions as possible graph edit operations. We will restrict these operations to two special types of operations.
These two are edge additions between two existing vertices in the graph, and a vertex addition connecting this new vertex to one of the already existing vertices.
This is to ensure that we get no disconnected parts and the resulting graphs are connected. With this restriction upon the set of possible edit operation, one cannot always
expect to be able to transform an arbitrary graph $g_1$ into $g_2$. However if we restrict the domain so that $g_1 \subseteq g_2$ or vice-versa, it is always possible to transform
one into the other without considering vertex deletions for example.

A cost is usually assigned to each edit operation. Let $e$ be the edit operation and let $c(e)$ denote the cost of performing the operation upon a graph. In our case we will
have a uniform cost of $1$. The cost of a sequence of edit operations $s=e_1, ..., e_n$ is then defined as $c(s)=\sum_{i=1}^{n} c(e_i)$. 
Denote by $\theta(g_1, g_2)$ the set of possible edit operation sequences transforming $g_1$ into $g_2$.

Using this we may define the distance between two graphs as: $d(g_1, g_2)=\underset{s \in \theta(g_1,g_2)}{\min c(s)}$. 
to $g_2$. That is, the distance between two graphs with the minimal cost of transforming one graph into another. It can be shown that this function satisfies the four properties of a metric~\cite{BunkeAll}.

Using the graph edit distance metric, we will also define the ball of a certain radius r to be the set of all graphs which are at most r edit operations away from the graph.
That is, $B(G,r)=\{G' \in \mathcal{G} | d(G, G') \le r  \}$.


A \emph{graph database} $\mathcal{D}=\{G_1, ..., G_n\}$ is a set of graphs. Given a graph $G \in \mathcal{G}$ and a graph database $\mathcal{D}$, we define the \emph{projected database} 
as the set of supergraphs of $G$. We denote this set as $\mathcal{D}_G=\{G'\in\mathcal{D} | G \subseteq G'  \}$.
The cardinality of the projected database is called the \emph{frequency} of the graph $G$ in the graph database $\mathcal{D}$ and is denoted by $freq(G)=|\mathcal{D}_G|$. 


We may now define the \emph{support} of the graph $G$ as $supp(G)=\dfrac{freq(G)}{|\mathcal{D}|}$.
A graph $G$ will be called a \emph{frequent subgraph} in $\mathcal{D}$ if $supp(G) \ge \sigma$ where $\sigma$ is some minimum support threshold, $0 \leq \sigma \leq 1$.

Let $\mathcal{S}$ be the set of frequent subgraphs of the graph database $\mathcal{D}$ for some minimum support threshold $\sigma$. That is, $\mathcal{S}=\{ G \in\mathcal{D} | supp(G) \ge \sigma  \}$

For any given pair of graphs $g_1$ and $g_2$, the \emph{Pearson's Correlation Coefficient}, $\theta(g_1, g_2)$, is defined as in \cite{FreqSubgraphPearson}: 
\begin{equation}
\dfrac{supp(g_1, g_2)-supp(g_1)supp(g_2)}
{\sqrt {supp(g_1)supp(g_2)(1-supp(g_1))(1-supp(g_2))} }
\end{equation}

Finally, the neighbourhood of a vertex $v$ in a graph $G$ will be denoted by $N_G(v)$ or simply $N(v)$ when it is clear which graph is meant. The neighbourhood of $v$ is the induced subgraph of the vertices
which are adjacent to $v$ in the graph $G$.

\subsection{Formal graph prediction problem formulation}
\label{sec:problemdefinition}
We define the problem as follows. Given a graph database $\mathcal{D}$ we want to find a certain discrete probability distribution. This distribution is an estimate of how probable a certain edit operation upon the current partial graph is.
Let $G_p \subset G$ be called the partial graph which is a subgraph of some unknown supergraph $G$. The \emph{set of all possible next graphs} given a partial graph
is the ball of radius one around the partial graph using the graph edit distance metric. That is, the set of all possible next graphs is $B(G_p, 1)$.
We want to find the actual next graph $G_p' \in B(G_p, 1)$ which is the result of performing some edit operation upon $G_p$. 
